package problem354;

//354.俄罗斯套娃信封问题
//https://leetcode.cn/problems/russian-doll-envelopes/description/

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

class Solution {
    public int maxEnvelopes(int[][] envelopes) {
        int n = envelopes.length;
        int[] dp = new int[n];
        dp[0] = 1;
        List<int[]> list = new ArrayList<>();
        Arrays.sort(envelopes,(a, b)->{
            if(a[0] != b[0]) return a[0]-b[0];
            return b[1] - a[1];
        });
        list.add(envelopes[0]);
        for(int i = 0; i<n; i++) {
            System.out.print("[" + envelopes[i][0] + "," + envelopes[i][1] + "], ");
        }
        System.out.println();

        for(int i = 1; i<n; i++) {
            int[] tmp = list.get(list.size()-1);
            if(envelopes[i][0] > tmp[0] && envelopes[i][1] > tmp[1]) {
                list.add(envelopes[i]);
            }else {
                int index = binarySearch(list, envelopes[i]);
                list.set(index,envelopes[i]);
            }
        }

        return list.size();
    }
    public int binarySearch(List<int[]> list, int[] arr) {
        int left = 0, right = list.size()-1;
        while(left < right) {
            int mid = left + (right - left) / 2;
            int[] tmp = list.get(mid);
            if(arr[0] > tmp[0] && arr[1] > tmp[1]) {
                left = mid+1;
            }else {
                right = mid;
            }
        }
        return left;
    }
}

/*
dp[i]: 以第i个信封为结尾的对多个数
*/